package top.lywivan.stack;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @desc 单调递减栈
 * @author:ivan.liu
 */
public class MonotonicityStack {

    /**
     * 给定一个数组，返回数组左边第一个小于自己的数所组成的数组
     * 如果左边都比自己小，则返回-1
     * @param src
     * @return
     */
    private int[] getLeftMinNum(int[] src){
        int[] res=new int[src.length];

        Deque<Integer> stack=new ArrayDeque<>();

        for (int i = 0; i < src.length; i++) {
            while (!stack.isEmpty()&&stack.peek()>=src[i]){
                stack.pop();
            }
            if(stack.isEmpty()){
                res[i]=-1;
            }else{
                res[i]=stack.peek();
            }
            stack.push(src[i]);
        }
        return res;
    }

    /**
     * 单调栈+哨兵
     * 哨兵：代表了一种边界情况，所以一般可以用哨兵来减少一些边界判断
     * @param src
     * @return
     */
    private int[] getLeftMinNumOptimize(int[] src) {
        int[] res=new int[src.length];

        Deque<Integer> stack=new ArrayDeque<>();
        stack.push(-1);

        for (int i = 0; i < src.length; i++) {
            while (stack.peek()>=src[i]){
                stack.pop();
            }
            res[i]=stack.peek();
            stack.push(src[i]);
        }
        return res;
    }

        public static void main(String[] args) {
        int[] param = new int[]{6,10,3,7,4,4,12,5};
        System.out.println(Arrays.toString(new MonotonicityStack().getLeftMinNumOptimize(param)));
    }
}
